#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5;

ll lcm(ll a,ll b){
    return a*b/__gcd(a,b);
}

ll findp(ll x){
    for(ll i=2;i<=sqrt(x);i++){
        if(x%i==0)return i;
    }
    return x;
}

ll solve(){
    ll x,y;
    cin>>x>>y;
    if(x==y) return 0;
    if(x<y)swap(x,y);
    if(x%y==0) return x;
    if(__gcd(x,y)!=1) return x+y;
    ll x_p=findp(x),y_p=findp(y);
    ll r1=lcm(x,y);
    ll r2=lcm(x,2)+lcm(2,y);
    ll r3=lcm(x,x_p)+lcm(x_p,y);
    ll r4=lcm(x,y_p)+lcm(y_p,y);
    ll r5=lcm(x,x_p)+lcm(2,x_p)+lcm(2,y);
    ll r6=lcm(x,2)+lcm(2,y_p)+lcm(y_p,y);
    ll r7=lcm(x,x_p)+lcm(x_p,y_p)+lcm(y_p,y);
    ll r8=lcm(x,x_p)+lcm(x_p,2)+lcm(2,y_p)+lcm(y_p,y);
    ll res=min({r1,r2,r3,r4,r5,r6,r7,r8});
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    while(n--){
        cout<<solve()<<'\n';
    }
    return 0;
}